package com.ly.algorithm.leetcode.binarysearch;

/**
 * @Classname Problem35
 * @Description
 *
 * 示例 1:
 *
 * 输入: [1,3,5,6], 5
 * 输出: 2
 * 示例 2:
 *
 * 输入: [1,3,5,6], 2
 * 输出: 1
 * 示例 3:
 *
 * 输入: [1,3,5,6], 7
 * 输出: 4
 * 示例 4:
 *
 * 输入: [1,3,5,6], 0
 * 输出: 0
 *
 * @Date 2020/12/20 16:06
 * @Author 冷心影翼
 */
public class Problem35 {

	public static void main(String[] args) {
		Solution35 solution35 = new Solution35();
		System.out.println(solution35.searchInsert(new int[]{1, 3, 5, 6}, 4));
	}

}


class Solution35 {
	public int searchInsert(int[] nums, int target) {
		int l = 0;
		int r = nums.length;
		while (l<r) {
			int mid = (l+r)/2;
			if(nums[mid] == target) {
				return mid;
			}
			if(target > nums[mid]) {
				l = mid+1;
			}else {
				r = mid;
			}
		}
		if(l-1<0)
			return 0;
		if(nums[l-1] > target)
			return l-1;
		else
			return l;
	}
}
